Abstract: A Suffix Tree (ST) is a --now classical-- data structure, computable in linear time, which represents the most algorithmically appropriate way to store a string, in order to face problems like the Exact String Matching Problem (ESM) or the Longest Common Exact Substring Problem (LCES). Even if very efficient in solving these problems, the ST data structure suffers from an important drawback, when dealing with an Approximate String Matching Problem (ASM) or with the harder Longest Common Approximate Substring Problem (LCAS), as only exact matching can be used in visiting a ST. In the approximate cases, a suitable notion of distance (most frequently Hamming or Levenshtein distances) must come into play. However, in the literature, there is no universally accepted data structure capable to deal with approximate searches just by performing algorithmic manipulations similar to ST’s. This makes necessary, when using ST's in an approximate context, taking into account errors by using unnatural and complicate strategies, inevitably leading to cumbersome algorithms.

Abstract: Missing

Abstract: Missing

Abstract: The central theme of our work is related to problem of formulating a “unitary step” that defines how a complex biological system makes a transition from one “state” or one “control mode” to another, as well as the conditions under which such transitions are enabled. This is because we recognize that automata (either discrete or hybrid, that is capable of modeling a mixed discrete/continuous behaviour), based on the formulation of these unitary steps, can elegantly model biological control mechanisms, allow us to reason about such mechanisms in a modal logic systems with modes constructed over a next-time operator, and can become the foundational framework for the emerging field of systems biology. These models can lead to more rigorous algorithmic analysis of large amounts of biological data, produced as (numerical) traces of in vivo, in vitro and in silico experiments—currently a central activity for many biologists and biochemists. Since modeling biological systems requires a careful consideration of both qualitative and quantitative aspects, our automata-based tools can effectively assist the working biologists to make predictions, generate falsifiable hypotheses and design wellfocused experiments—activities in which the time dimension and a properly designed query language cannot be left out of consideration. Thus, ultimately, the aim of our work is to elucidate the role played by automata in modeling biological systems and to investigate the potential of such tools when combined with more “classical” approaches used in the past to devise models and experiments in biology. Our discussion here is based primarily on our experience with a novel system that we introduced recently (called, XS-systems) and used it to implement algorithms and software tools (Simpathica). These conceptual tools have been integrated with prototype implementations, and are currently undergoing many interesting and growing sets of enhancements and optimizations

Abstract: Missing

Abstract: Missing